use std::cmp::{max, Ordering, Reverse};
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, LinkedList};

struct Solution;
impl Solution {
    //1047
    pub fn min_cost(n: i32, cuts: Vec<i32>) -> i32 {
        let mut cuts = cuts;
        cuts.push(0);
        cuts.push(n);
        cuts.sort();
        let m = cuts.len();
        let mut dp = vec![vec![0; m]; m];

        //dp[i][j] = min(dp[i][k] + dp[k][j]) + cuts[j] - cuts[i]
        for i in (0..m).rev() {
            for j in i + 2..m {
                dp[i][j] = i32::MAX;
                for k in i + 1..j {
                    dp[i][j] = i32::min(dp[i][j], dp[i][k] + dp[k][j]);
                }
                dp[i][j] += cuts[j] - cuts[i];
            }
        }
        dp[0][m - 1]
    }
    //3249
    pub fn count_good_nodes(edges: Vec<Vec<i32>>) -> i32 {
        let mut map = vec![vec![]; edges.len() + 1];
        let mut ans = 0;

        for edge in edges {
            map[edge[0] as usize].push(edge[1] as usize);
            map[edge[1] as usize].push(edge[0] as usize);
        }

        fn dfs(map: &Vec<Vec<usize>>, root: usize, parent: usize, ans: &mut i32) -> i32 {
            let mut child_cnt = -1;
            let mut total = 0;
            let mut is_good = true;
            for &node in &map[root] {
                if node == parent {
                    continue;
                }
                let c = dfs(map, node, root, ans);
                total += c;
                if child_cnt == -1 {
                    child_cnt = c;
                    continue;
                }
                if child_cnt != c {
                    is_good = false;
                }
            }
            if is_good {
                *ans += 1;
            }
            total + 1
        }

        dfs(&map, 0, 0, &mut ans);
        ans
    }
    //3261
    pub fn count_k_constraint_substrings_3261(
        s: String,
        k: i32,
        queries: Vec<Vec<i32>>,
    ) -> Vec<i64> {
        let mut count = [0; 2];
        let mut right = vec![s.len(); s.len()];
        let mut prefix = vec![0; s.len() + 1];
        let s = s.as_bytes();
        let mut i = 0;
        for j in 0..s.len() {
            count[(s[j] - b'0') as usize] += 1;
            while count[0] > k && count[1] > k {
                right[i] = j;
                count[(s[i] - b'0') as usize] -= 1;
                i += 1;
            }
            prefix[j + 1] = prefix[j] + (j - i + 1);
        }
        let mut ans = Vec::with_capacity(queries.len());
        for q in &queries {
            let l = q[0] as usize;
            let r = q[1] as usize;
            let i = std::cmp::min(r + 1, right[l]);
            let part1 = (i - l + 1) * (i - l) / 2;
            let part2 = prefix[r + 1] - prefix[i];
            ans.push((part2 + part1) as i64);
        }
        ans
    }
    //3258
    pub fn count_k_constraint_substrings(s: String, k: i32) -> i32 {
        let mut i = 0;
        let mut count = [0; 2];
        let mut res = 0;
        let s = s.as_bytes();
        for j in 0..s.len() {
            count[s[j] as usize - b'0' as usize] += 1;
            while count[0] > k && count[1] > k {
                count[s[i] as usize - b'0' as usize] -= 1;
                i += 1;
            }
            res += (j - i + 1) as i32;
        }
        res
    }
    //3250
    pub fn count_of_pairs_3250(nums: Vec<i32>) -> i32 {
        //dp[i][j] += dp[i - 1][k] (k <= j)
        let mut dp = vec![[0; 51]; nums.len()];
        let m = 1000000007;
        dp[0][0..=nums[0] as usize].fill(1);
        for i in 1..nums.len() {
            for j in 0..=nums[i] as usize {
                for k in 0..=j as usize {
                    //k <= j
                    //nums[i - 1] - k >=  nums[i] - j
                    if nums[i - 1] as usize >= k {
                        if nums[i - 1] as usize - k >= nums[i] as usize - j {
                            dp[i][j] += dp[i - 1][k];
                            dp[i][j] %= m;
                        }
                        continue;
                    }
                    break;
                }
            }
        }
        dp[nums.len() - 1].iter().fold(0, |acc, &x| (acc + x) % m)
    }

    pub fn count_of_pairs(nums: Vec<i32>) -> i32 {
        let mut dp = vec![[0; 1001]; nums.len()];
        let m = 1000000007;
        dp[0][0..=nums[0] as usize].fill(1);
        for i in 1..nums.len() {
            let d = 0.max(nums[i] - nums[i - 1]) as usize;
            for j in d..=nums[i] as usize {
                if j == 0 {
                    dp[i][j] = dp[i - 1][j - d];
                } else {
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j - d];
                }
            }
        }
        dp[nums.len() - 1].iter().fold(0, |acc, &x| (acc + x) % m)
    }
    pub fn can_alice_win(nums: Vec<i32>) -> bool {
        let mut one = 0;
        let mut two = 0;
        nums.iter()
            .for_each(|&x| if x >= 10 { two += x } else { one += x });
        one != two
    }

    //51
    pub fn solve_n_queens_dfs(
        deep: usize,
        n: usize,
        y: i32,
        q: i32,
        r: i32,
        tmp: &mut Vec<String>,
        ans: &mut Vec<Vec<String>>,
    ) {
        if n == deep {
            ans.push(tmp.clone());
            return;
        }
        for i in 0..n {
            if ((y & (1 << i) == 0) && (q & (1 << i) == 0) && (r & (1 << i) == 0)) {
                unsafe {
                    tmp[deep].as_bytes_mut()[i] = b'Q';
                }
                Solution::solve_n_queens_dfs(
                    deep + 1,
                    n,
                    y | (1 << i),
                    (q | (1 << i)) << 1,
                    (r | (1 << i)) >> 1,
                    tmp,
                    ans,
                );
                unsafe {
                    tmp[deep].as_bytes_mut()[i] = b'.';
                }
            }
        }
    }
    pub fn solve_n_queens(n: i32) -> Vec<Vec<String>> {
        let mut tmp = vec![String::from(".".repeat(n as usize)); n as usize];
        let mut ans = Vec::new();
        Solution::solve_n_queens_dfs(0, n as usize, 0, 0, 0, &mut tmp, &mut ans);
        ans
    }
    pub fn total_n_queens_dfs(deep: usize, n: usize, y: i32, q: i32, r: i32, ans: &mut i32) {
        if n == deep {
            *ans += 1;
            return;
        }
        for i in 0..n {
            if ((y & (1 << i) == 0) && (q & (1 << i) == 0) && (r & (1 << i) == 0)) {
                Solution::total_n_queens_dfs(
                    deep + 1,
                    n,
                    y | (1 << i),
                    (q | (1 << i)) << 1,
                    (r | (1 << i)) >> 1,
                    ans,
                );
            }
        }
    }
    //52
    pub fn total_n_queens(n: i32) -> i32 {
        let mut ans = 0;
        Solution::total_n_queens_dfs(0, n as usize, 0, 0, 0, &mut ans);
        ans
    }

    pub fn check_two_chessboards(coordinate1: String, coordinate2: String) -> bool {
        let x1 = coordinate1.as_bytes()[0] - b'a' + 1;
        let y1 = coordinate1.as_bytes()[1] - b'1';
        let x2 = coordinate2.as_bytes()[0] - b'a' + 1;
        let y2 = coordinate2.as_bytes()[1] - b'1';

        (x1 ^ y1) & 1 == (x2 ^ y2) & 1
    }

    //688
    pub fn knight_probability(n: i32, k: i32, row: i32, column: i32) -> f64 {
        let mut dp = [[[0f64; 25]; 25]; 101];
        let dirs: [[i32; 2]; 8] = [
            [1, 2],
            [1, -2],
            [2, 1],
            [2, -1],
            [-1, 2],
            [-1, -2],
            [-2, 1],
            [-2, -1],
        ];
        dp[0].fill([1f64; 25]);
        //dp[k][i][j] += 1/8 * dp[k - 1][i+x][j+y];
        for step in 1..=k {
            for i in 0..n {
                for j in 0..n {
                    for dir in dirs {
                        if (0..n).contains(&(i + dir[0])) && (0..n).contains(&(j + dir[1])) {
                            dp[step as usize][i as usize][j as usize] += dp[(step - 1) as usize]
                                [(i + dir[0]) as usize][(j + dir[1]) as usize]
                                / 8.0;
                        }
                    }
                }
            }
        }
        dp[k as usize][row as usize][column as usize]
    }
    //2717
    pub fn semi_ordered_permutation(nums: Vec<i32>) -> i32 {
        let mut first_i = 0;
        let mut last_i = 0;

        for (i, &num) in nums.iter().enumerate() {
            if num == 1 {
                first_i = i;
            } else if num == nums.len() as i32 {
                last_i = i;
            }
        }
        let mut m = (first_i - 0 + nums.len() - 1 - last_i) as i32;
        if last_i < first_i {
            m -= 1;
        }
        m
    }
    //2931
    pub fn max_spending(values: Vec<Vec<i32>>) -> i64 {
        let mut values: Vec<i32> = values.iter().flatten().cloned().collect();
        values.sort_unstable();
        values
            .iter()
            .enumerate()
            .map(|(index, &value)| index as i64 * value as i64)
            .sum()
    }
    //3264
    pub fn get_final_state(nums: Vec<i32>, k: i32, multiplier: i32) -> Vec<i32> {
        use std::cmp::{max, Ordering, Reverse};
        use std::collections::BinaryHeap;
        let mut k = k;
        #[derive(Eq, PartialEq, Debug)]
        struct Pair(usize, i32);
        impl Ord for Pair {
            fn cmp(&self, other: &Self) -> Ordering {
                if self.1.eq(&other.1) {
                    return self.0.cmp(&other.0);
                }
                self.1.cmp(&other.1)
            }
        }
        impl PartialOrd for Pair {
            fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
                Some(self.cmp(other))
            }
        }
        let mut min_heap = BinaryHeap::new();
        nums.iter()
            .enumerate()
            .for_each(|(index, &num)| min_heap.push(Reverse(Pair(index, num))));
        while k > 0 {
            println!("{:?}", min_heap);
            let Reverse(mut top) = min_heap.pop().unwrap();
            top.1 *= multiplier;
            k -= 1;
            min_heap.push(Reverse(top));
            println!("{:?}", min_heap);
        }
        let mut ans = vec![0; nums.len()];
        min_heap.iter().for_each(|Reverse(num)| ans[num.0] = num.1);
        ans
    }

    pub fn edge_score(edges: Vec<i32>) -> i32 {
        let mut m = vec![0; edges.len()];
        let mut ans = (0, 0);
        edges.iter().enumerate().for_each(|(i, &x)| {
            let x = x as usize;
            m[x] += i;
            if m[x] > ans.0 || (m[x] == ans.0 && x < ans.1) {
                ans = (m[x], x)
            }
        });
        ans.1 as i32
    }
    //1014
    pub fn max_score_sightseeing_pair(values: Vec<i32>) -> i32 {
        let mut pre_max = 0;
        let mut ans = 0;
        values.iter().enumerate().for_each(|(i, &x)| {
            let i = i as i32;
            ans = ans.max(x - i + pre_max);
            pre_max = pre_max.max(x + i)
        });
        ans
    }
    pub fn maximum_subsequence_count(text: String, pattern: String) -> i64 {
        let mut cnt_a = 0;
        let mut cnt_b = 0;
        let pattern = pattern.as_bytes();
        let mut ans = 0;
        text.as_bytes().iter().for_each(|&c| {
            if pattern[0] == pattern[1] && c == pattern[0] {
                ans += cnt_a;
                cnt_a += 1;
            } else if c == pattern[0] {
                cnt_a += 1;
            } else if c == pattern[1] {
                cnt_b += 1;
                ans += cnt_a
            }
        });
        ans + cnt_a.max(cnt_b)
    }
    //2306
    pub fn distinct_names(ideas: Vec<String>) -> i64 {
        let mut m = HashMap::new();
        let mut ans: i64 = 0;
        ideas.iter().for_each(|idea| {
            m.entry(&idea[1..])
                .or_insert(HashSet::new())
                .insert(&idea[0..1]);
        });
        for (k1, v1) in &m {
            for (k2, v2) in &m {
                if k1 == k2 {
                    continue;
                }
                let sub = v1.intersection(&v2).count();
                ans += ((v1.len() - sub) * (v2.len() - sub)) as i64;
            }
        }
        ans
    }
    //https://leetcode.cn/problems/palindrome-partitioning/?envType=daily-question&envId=2025-02-25
    //131
    fn partition_chk(s: &[u8]) -> bool {
        let (mut i, mut j) = (0, (s.len() - 1) as i32);
        while i < j {
            if s[i as usize] != s[j as usize] {
                return false;
            }
            i += 1;
            j -= 1;
        }
        true
    }
    fn partition_u8(s: &[u8]) -> Vec<Vec<String>> {
        if s.len() == 1 {
            return vec![vec![String::from_utf8(s.to_vec()).unwrap().to_string()]];
        }
        let mut vec = Vec::new();
        for i in 1..=s.len() {
            if Self::partition_chk(&s[..i]) {
                for v in Self::partition_u8(&s[i..]) {
                    let mut new_v = vec![String::from_utf8(s[..i].to_vec()).unwrap()];
                    new_v.extend(v);
                    vec.push(new_v);
                }
            }
        }
        vec
    }
    pub fn partition(s: String) -> Vec<Vec<String>> {
        Self::partition_u8(s.as_bytes())
    }

    //https://leetcode.cn/problems/palindrome-partitioning-ii/?envType=daily-question&envId=2025-02-25
    pub fn min_cut(s: String) -> i32 {
        let s = s.as_bytes();
        let mut p = vec![vec![true; s.len()]; s.len()];
        //p[i][j] = (s[i] == [j]) && p[i+1][j-1]
        for i in (0..s.len()).rev() {
            for j in i + 1..s.len() {
                p[i][j] = (s[i] == s[j]) && p[i + 1][j - 1]
            }
        }
        let mut f = vec![0; s.len()];
        for i in 0..s.len() {
            if p[0][i] {
                f[i] = 0;
                continue;
            }
            f[i] = s.len();
            for j in 0..i {
                if p[j + 1][i] {
                    f[i] = f[i].min(f[j] + 1);
                }
            }
        }
        f[s.len() - 1] as i32
    }

    //f[i][j] i结束的位置，切割j次的最小修改数量，分成k部分，技切割k-1次
    //g[i][j] i j 是回文的最小修改次数
    pub fn palindrome_partition(s: String, k: i32) -> i32 {
        let s = s.as_bytes();
        let mut g = vec![vec![0; s.len()]; s.len()];
        //g[i][j] = s[i] == s[j] ? g[i+1][j-1], g[i+1][j-1] + 1
        for i in (0..s.len()).rev() {
            for j in i + 1..s.len() {
                g[i][j] = g[i + 1][j - 1];
                if s[i] != s[j] {
                    g[i][j] += 1
                }
            }
        }
        let mut f = vec![vec![s.len() as i32; k as usize]; s.len()];
        (0..s.len()).for_each(|i| f[i][0] = g[0][i]);

        //
        //f[i][j] = MIN(f[m][j-1] + g[m+1][i]) m E [0..i)
        for j in 1..k as usize {
            for i in j..s.len() {
                for m in 0..i {
                    f[i][j] = f[i][j].min(f[m][j - 1] + g[m + 1][i]);
                }
            }
        }
        f[s.len() - 1][(k - 1) as usize]
    }

    pub fn check_partitioning(s: String) -> bool {
        let s = s.as_bytes();
        let mut g = vec![vec![true; s.len()]; s.len()];
        for i in (0..s.len()).rev() {
            for j in i + 1..s.len() {
                g[i][j] = (s[i] == s[j]) && g[i + 1][j - 1];
            }
        }
        let mut f = vec![vec![false; 3]; s.len()];
        (0..s.len()).for_each(|i| f[i][0] = g[0][i]);
        //f[i][j] |= f[m][j - 1] && g[m + 1][i]
        for j in 1..3 {
            for i in j..s.len() {
                for m in 0..i {
                    f[i][j] |= f[m][j - 1] && g[m + 1][i];
                }
            }
        }
        f[s.len()][2]
    }
    pub fn break_palindrome(palindrome: String) -> String {
        if palindrome.len() == 1 {
            return "".to_string();
        }
        let mut s = palindrome.as_bytes().to_vec();
        for i in 0..s.len() / 2 {
            if s[i] != 'a' as u8 {
                s[i] = 'a' as u8;
                return String::from_utf8(s).unwrap();
            }
        }
        *s.last_mut().unwrap() = 'b' as u8;
        String::from_utf8(s).unwrap()
    }
    pub fn beautiful_subarrays(nums: Vec<i32>) -> i64 {
        let mut hash = HashMap::new();
        let mut cur = 0;
        let mut ans = 0;
        hash.insert(0, 1);
        for num in nums {
            cur = cur ^ num;
            ans += hash.get(&cur).unwrap_or(&0);
            *hash.entry(cur).or_insert(0) += 1;
        }
        ans
    }
}

struct Allocator {
    n: usize,
    id2pos: BTreeMap<i32, LinkedList<usize>>,
    used: BTreeMap<usize, usize>,
}

impl Allocator {
    fn new(n: i32) -> Self {
        return Self {
            n: n as usize,
            id2pos: BTreeMap::new(),
            used: BTreeMap::new(),
        };
    }

    fn allocate(&mut self, size: i32, m_id: i32) -> i32 {
        let mut start = 0;
        for (&i, &used) in self.used.iter() {
            if start == i {
                start = i + used;
                continue;
            }
            if i - start >= size as usize {
                self.id2pos.entry(m_id).or_default().push_back(start);
                self.used.insert(start, size as usize);
                return start as i32;
            }
            start = i + used;
        }
        if self.n - start >= size as usize {
            self.id2pos.entry(m_id).or_default().push_back(start);
            self.used.insert(start, size as usize);
            return start as i32;
        }
        -1
    }

    fn free_memory(&mut self, m_id: i32) -> i32 {
        self.id2pos
            .remove(&m_id)
            .map(|v| v.iter().map(|&i| self.used.remove(&i).unwrap()).sum())
            .unwrap_or(0) as i32
    }
}

struct BrowserHistory {
    vec: Vec<String>,
    cur: usize,
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl BrowserHistory {
    fn new(homepage: String) -> Self {
        Self {
            vec: vec![homepage; 1],
            cur: 0,
        }
    }

    fn visit(&mut self, url: String) {
        self.vec.truncate(self.cur + 1);
        self.vec.push(url);
        self.cur += 1;
    }

    fn back(&mut self, steps: i32) -> String {
        self.cur -= self.cur.min(steps as usize);
        self.vec[self.cur].clone()
    }

    fn forward(&mut self, steps: i32) -> String {
        self.cur = (self.vec.len() - 1).min(self.cur + steps as usize);
        self.vec[self.cur].clone()
    }
}

//https://leetcode.cn/problems/design-a-text-editor/description/?envType=daily-question&envId=2025-02-25
struct TextEditor {
    left: Vec<char>,
    right: Vec<char>,
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl TextEditor {
    fn new() -> Self {
        Self {
            left: Vec::with_capacity(20000),
            right: Vec::with_capacity(20000),
        }
    }

    fn add_text(&mut self, text: String) {
        self.left.extend(text.chars());
    }

    fn delete_text(&mut self, k: i32) -> i32 {
        let n = self.left.len();
        self.left.truncate(n - n.min(k as usize));
        (n - self.left.len()) as i32
    }

    fn cursor_left(&mut self, k: i32) -> String {
        self.left
            .drain(self.left.len().saturating_sub(k as usize)..)
            .rev()
            .for_each(|c| self.right.push(c));
        self.left[self.left.len().saturating_sub(10)..]
            .iter()
            .collect()
    }
    fn cursor_right(&mut self, k: i32) -> String {
        self.right
            .drain(self.right.len().saturating_sub(k as usize)..)
            .rev()
            .for_each(|c| self.left.push(c));
        self.left[self.left.len().saturating_sub(10)..]
            .iter()
            .collect::<String>()
    }
}

//https://leetcode.cn/problems/design-a-food-rating-system/description/?envType=daily-question&envId=2025-02-25
struct FoodRatings {
    food_m: HashMap<String, (i32, String)>,
    cuisine_m: BTreeMap<String, BTreeSet<(i32, String)>>,
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl FoodRatings {
    fn new(foods: Vec<String>, cuisines: Vec<String>, ratings: Vec<i32>) -> Self {
        let mut st = Self {
            food_m: HashMap::new(),
            cuisine_m: BTreeMap::new(),
        };
        foods.iter().enumerate().for_each(|(i, k)| {
            st.food_m
                .insert(k.clone(), (ratings[i], cuisines[i].clone()));
            st.cuisine_m
                .entry(cuisines[i].clone())
                .or_insert(BTreeSet::new())
                .insert((-ratings[i], k.clone()));
        });
        st
    }

    fn change_rating(&mut self, food: String, new_rating: i32) {
        let item = self.food_m.get_mut(&food).unwrap();
        let m = self.cuisine_m.get_mut(&item.1).unwrap();
        m.remove(&(-item.0, food.clone()));
        item.0 = new_rating;
        m.insert((-item.0, food.clone()));
    }

    fn highest_rated(&self, cuisine: String) -> String {
        self.cuisine_m
            .get(&cuisine)
            .unwrap()
            .first()
            .unwrap()
            .1
            .clone()
    }
}

fn main() {
    println!("{}", Solution::count_of_pairs([2, 3, 2].to_vec()));
    println!("{}", Solution::count_of_pairs([5, 5, 5, 5].to_vec()));
    println!("{:#?}", Solution::total_n_queens(4));
    println!("{}", Solution::knight_probability(3, 2, 0, 0));
    println!("{}", Solution::knight_probability(1, 0, 0, 0));
    println!(
        "{:?}",
        Solution::get_final_state([2, 1, 3, 5, 6].to_vec(), 5, 2)
    );
    println!("{:?}", Solution::get_final_state([1, 3, 5].to_vec(), 5, 3));

    println!(
        "{:?}",
        Solution::max_score_sightseeing_pair(vec![8, 1, 5, 2, 6])
    );
    println!("{:?}", Solution::maximum_subsequence_count(
        "vnedkpkkyxelxqptfwuzcjhqmwagvrglkeivowvbjdoyydnjrqrqejoyptzoklaxcjxbrrfmpdxckfjzahparhpanwqfjrpbslsyiwbldnpjqishlsuagevjmiyktgofvnyncizswldwnngnkifmaxbmospdeslxirofgqouaapfgltgqxdhurxljcepdpndqqgfwkfiqrwuwxfamciyweehktaegynfumwnhrgrhcluenpnoieqdivznrjljcotysnlylyswvdlkgsvrotavnkifwmnvgagjykxgwaimavqsxuitknmbxppgzfwtjdvegapcplreokicxcsbdrsyfpustpxxssnouifkypwqrywprjlyddrggkcglbgcrbihgpxxosmejchmzkydhquevpschkpyulqxgduqkqgwnsowxrmgqbmltrltzqmmpjilpfxocflpkwithsjlljxdygfvstvwqsyxlkknmgpppupgjvfgmxnwmvrfuwcrsadomyddazlonjyjdeswwznkaeaasyvurpgyvjsiltiykwquesfjmuswjlrphsdthmuqkrhynmqnfqdlwnwesdmiiqvcpingbcgcsvqmsmskesrajqwmgtdoktreqssutpudfykriqhblntfabspbeddpdkownehqszbmddizdgtqmobirwbopmoqzwydnpqnvkwadajbecmajilzkfwjnpfyamudpppuxhlcngkign".to_string(),
        "rr".to_string(),
    ));
    println!(
        "{:?}",
        Solution::distinct_names(
            vec!["coffee", "donuts", "time", "toffee"]
                .iter()
                .map(|s| s.to_string())
                .collect()
        )
    );
    let s = "1234".to_string();
    println!("{}", &s[1..2]);
}

use std::io::{self, Write};
use std::ops::Add;
use std::thread::park;

fn zailgo_level_one_hint(p: &str, n: usize) -> String {
    if n <= 1 {
        return p.to_string();
    }

    let mut f = String::with_capacity(p.len());
    f.extend(std::iter::repeat('\0').take(p.len() * n));

    let c = 2 * (n - 1);
    let mut i = 0;

    for (j, &b) in p.as_bytes().iter().enumerate() {
        let pos = if i < n {
            j * c + i
        } else {
            (i - n + 1) * 2 + j * c - ((i - n + 1) * 2)
        };
        if pos < f.len() {
            unsafe {
                f.as_bytes_mut()[pos] = b;
            }
        }
        i = (i + 1) % c;
    }

    f.chars().filter(|&c| c != '\0').collect()
}
